//
// Problem 1: gas stations
//
// Created by tianq on 24-12-4.
//

#include <iostream>
#include <vector>
#include <random>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    int n, k;  // n: fuel tank size, k: gas stations count
    vector<int> distances; // distance[0] means road from station 0 (start) to station 1

    // cin >> n >> k;
    // for (int i = 0; i < k; i++){
    //     int tmp = 0;
    //     cin >> tmp;
    //     distances.emplace_back(tmp);
    // }

    // generate test data
    n = 100, k = 10;
    random_device rd;
    mt19937_64 rng(rd());
    uniform_int_distribution int_dist(0, n); // [0,n]: our car can not go further than tank capacity n
    for (int i = 0; i <= k; i++) // 0: start, [1,k]: gas station, k+1: destination, we stops there, so no further roads
        distances.push_back(int_dist(rng));

    // echo input
    cout << "problem 1 plus" << endl;
    cout << "tank size: " << n << endl;
    cout << "gas station count: " << k << endl;
    for (int i = 0; i <= k + 1; i++) cout << i << "\t";
    cout << endl;
    for (int i = 0; i <= k; i++) cout << "    " << distances[i] << "\t";
    cout << endl;

    // Lite Version, only counts
    // states[tankRemain]=int RefillCount
    // start:states[100]=0, we got our tanked filled on leaving
    // next station: 30km ahead
    // create an empty map for new states
    // for each states with tankRemain < 30, we can't reach next station, drop
    // else, update newStates[100-30]=0 (no refill), newStates[100]=1 (refilled)
    // newStates[tankRemain-ahead]=RefillCount (no refill),
    // newStates[tankVolume]=RefillCount+1 (refilled)

    int minRefill = numeric_limits<int>::max();
    unordered_map<int, int> map; // <GasRemain,RefillCount>
    map.emplace(n, 0);

    for (const int &ahead: distances) {
        unordered_map<int, int> newMap; // <GasRemain,RefillCount>
        minRefill = numeric_limits<int>::max();
        for (const auto &[remain, refill]: map) {
            if (remain < ahead) continue; // we can't reach next station
            if (refill < minRefill) minRefill = refill;

            if (int curRemain = remain - ahead;
                !newMap.contains(curRemain) || refill < newMap[curRemain]) {
                newMap[curRemain] = refill;
            }

            if (!newMap.contains(n) || refill + 1 < newMap[n])
                newMap[n] = refill + 1;
        }

        cout << endl << "ahead: " << ahead << ", min refill: " << minRefill << endl;
        for (const auto &[key,val]: newMap) {
            cout << "Remain: " << key << "\t Count: " << val << endl;
        }

        map = newMap;
    }

    cout << endl << "result:" << endl;
    cout << minRefill << endl;

    return 0;
}
